Modern data processing systems generally use magnetic disc storage systems for storing therein an operating system program and data. Such a disc storage system may comprise an array of disc drives, with each disc drive having a plurality of discs and associated magnetic heads for each of the two magnetic surfaces of each disc.
"Caching" of logical data blocks retrieved from the disc drive array is often done to improve the average access time of the disc drive array to requests for logical data blocks from the host data processing system. Caching is a technique that puts a small, fast memory, called a cache memory, in front of a large, slow memory, such as the disc drive array, in such a way that the resulting combination approximates a large, fast memory.
"Prefetch blocks" are the logical data blocks that the host system has not requested, but are read from the discs in the array into the cache memory because a high probability exists that the host will request them in the near future. In this way, the stored prefetch blocks are available from the cache memory in response to a subsequent request from the host without reaccessing the disc drive array.
Logical block numbers (LBN's) provide a means for the host system to address physical data on the disc drives without having to be concerned with the physical attributes of the disc drives. The logical data blocks are stored in the disc drive address with a physical block location that is mapped to correspond to a drive, band, cylinder, sector address in the array. A cylinder is made up of all of the tracks that can be accessed in the array without the need for a seek. For instance, if the disc drive array has five discs so that the array can access ten disc surfaces, it will typically have ten heads. The ten tracks that align beneath those heads at one time make up a cylinder.
A read operation can be viewed as a three step process. The first step is to perform a "seek" operation to move the heads to the correct cylinder. The second step is to wait for the disk to rotate around so that the requested LBN passes under the head. This time is termed "rotational latency." The final step is to read the requested LBN as it passes under the head. Because of the sequential way that user processes for the host system access many files, and the policies that operating systems in the data processing systems use to allocate files, there is a tendency for the disc drive array to first see a request for a set of logical data blocks and then shortly after see a request for another set of logical data blocks starting with the block whose LBN is one greater than the last LBN of the first requested set of logical blocks.
To best utilize the capabilities of the cache memory, it is therefore important to prefetch the logical blocks whose LBNs are greater (by a small amount) than the last logical blocks retrieved by a current request from the host. Traditional block ordering schemes order the LBN's so as to pass under the head in increasing order. When combined with read-ahead caching, these strategies require the heads to stay locked on the cylinder after the desired logical blocks have been read in order to access the read-ahead blocks. This is time that could otherwise be used to begin satisfying subsequent requests.